package chapter24;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 单源最短路径-BellmanFord
 */
public class SingleSource_BellmanFord {

    public static boolean bellmanFord(Graph G, EdgeNode s) {
        initializeSingleSource(G, s);
        for (int i = 0; i < G.numVertexes; i++) {
            for (VertexNode vertexNode : G.adjList) {
                EdgeNode u = vertexNode.firstEdge;
                EdgeNode v = u.next;
                while (v != null) {
                    EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                    relax(u, v1, v.weight);
                    v = v.next;
                }
            }
        }
        for (VertexNode vertexNode : G.adjList) {
            EdgeNode u = vertexNode.firstEdge;
            EdgeNode v = u.next;
            while (v != null) {
                EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                if (v1.d > u.d + v.weight) {
                    return false;
                }
                v = v.next;
            }
        }
        return true;
    }

    public static void initializeSingleSource(Graph G, EdgeNode s) {
        for (VertexNode v : G.adjList) {
            v.firstEdge.d = Integer.MAX_VALUE;
            v.firstEdge.pai = null;
        }
        s.firstEdge.d = 0;
    }

    public static void relax(EdgeNode u, EdgeNode v, int w) {
        if (v.d > u.d + w) {
            v.d = u.d + w;
            v.pai = u;
        }
    }

    public static void insert(EdgeNode x, EdgeNode y, int w) {
        EdgeNode pre = x;
        while (pre.next != null) {
            pre = pre.next;
        }
        y.firstEdge = x;
        y.weight = w;
        pre.next = y;
    }

    public static class EdgeNode {
        public char key;
        public int weight;
        public EdgeNode firstEdge = this;
        public EdgeNode next;
        public int adj;
        public int d = Integer.MAX_VALUE;
        public EdgeNode pai;

        public EdgeNode(char key, int adj) {
            this.key = key;
            this.adj = adj;
        }

        public int getWeight() {
            return weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EdgeNode edgeNode = (EdgeNode) o;
            return Objects.equals(key, edgeNode.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public String toString() {
            return "{" +
                    "u='" + firstEdge.key + '\'' +
                    ", v='" + key + '\'' +
                    ", d=" + d +
                    '}';
        }
    }

    public static class VertexNode {
        public String key;
        public EdgeNode firstEdge;

        public VertexNode(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "key='" + key + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }
    }

    public static class Graph {
        public List<VertexNode> adjList = new ArrayList<>();
        public int numVertexes;
        public int numEdges;

        @Override
        public String toString() {
            return "Graph{" +
                    "adjList=" + adjList +
                    ", numVertexes=" + numVertexes +
                    ", numEdges=" + numEdges +
                    '}';
        }
    }
}
